﻿// 3804. 构造字符串.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3807/
给定一个长度为 n
 的由小写字母构成的字符串 s
。

请你构造一个长度为 k
 的由小写字母构成的字符串 t
。

要求，字符串 t
 需满足：

字符串 t
 在字典序上大于字符串 s
。
字符串 t
 的字母集是字符串 s
 的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的字母集为 {a,b,d}
。
字符串 t
 在字典序上尽可能小。
保证答案存在。

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据第一行包含两个整数 n
 和 k
。

第二行包含一个长度为 n
 的字符串表示 s
。

输出格式
每组数据输出一行满足所有条件的字符串 t
。

数据范围
前三个测试点满足 1≤n,k≤3
。
所有测试点满足 1≤T≤10
，1≤n,k≤105
。
同一测试点内，所有 n
 的和不超过 105
，所有 k
 的和不超过 105
。

输入样例：
4
3 3
abc
3 2
abc
3 3
ayy
2 3
ba
输出样例：
aca
ac
yaa
baa
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 